1. Field of the Invention
This invention relates to guidance and control methods for automatically guided vehicle (AGV) systems such as mobile robots and more specifically to methods for coordinating the motion of free-roving vehicles by closing the control loop between stationary control computers and mobile control computers.
2. Related Art
Automatically guided vehicle (AGV) systems typically use a guidance scheme which allows the vehicles to travel only forward or backward along a fixed path. This path normally is defined by a guide wire buried in the factory floor, as disclosed in U.S. Pat. No. 4530056. Such a scheme requires elaborate installation methods, as disclosed in U.S. Pat. Nos. 4554724 and 4562635. Alternative AGV guidance and control methods have included means of detecting markings along an AGV's path, such as the methods described in U.S. Pat. Nos. 4593238 and 4593239. Still other methods require a scanner-equipped AGV to follow an ultraviolet-reflective stripe painted on the floor. More recent technological developments have included methods using rotating laser-optical tracking wherein coded reflective tags are placed at points along allowable routes and AGV-based systems illuminate and observe these tags, using conventional triangulation to determine the AGV's position. Inertial guidance methods have many advantages, but in the final analysis still require periodic absolute position updating by such means as those described. All these prior methods involve installing either a continuous physical guide means or physical guide targets throughout the factory, either on or in the floor or on or adjacent to machines, load stations, critical points, or the like. Even where the AGVs incorporate on-board dead reckoning capabilities, these schemes make AGV systems difficult or time-consuming to install, program, or modify.
Significant operational problems also plague systems with existing guidance schemes. For example, dead spots (areas where physical obstructions obscure the guide markers or electrical interference hinders radio or wire-guided communications) can cause loss of AGV control. Grid-lock or deadlock also can occur in wire-guided systems where one AGV "dies" and other AGVs can't pass it, or where two AGVs approach an intersection from different directions.
Texas Instruments designed and reduced to practice a more autonomous guidance arrangement (described in U.S. patent application Ser. No. 771,397 discussed above) which used a form of visual navigation system to update the position references of AGVs equipped with automatic dead reckoning ability. That system incorporates the means to view multiple independently guided and steered AGVs operating within the same environment without physical path constraints. The AGVs in that system incorporate on-board dead reckoning guidance. The visual navigation system disclosed herein acts to close the guidance servo loop by providing the AGVs with periodic absolute position updates.
The only constraints on the AGVs in this scheme are that they be operative and visible (their beacons must be lighted and they must be within the field of view of any of the system guidance cameras). Such a system is superior to prior art in a number of ways: no guide strip or implanted wire need be installed in or on the factory floor; the AGVs are not constrained to one- or two-directional movement but can be free-roving; the AGV pathways are readily reprogrammable.
The TI Visual Navigation System disclosed in U.S. patent application Ser. No. 771,397 operated without any knowledge of where the AGV should be. It used the method that at any instant when the vision system was taking a picture, there was only the AGV of interest whose light beacons turned on. Therefore, the lights captured by the vision system at that instant must be the AGV of interest. It then computed each light's centroid and transformed all 3 centroids from camera (image-plane) coordinates to factory floor coordinates. Using the stored triangular shape and dimension to determine the AGV's position and orientation, the vision system passed this data through the communication link (described in U.S. patent application Ser. No. 771,322) to the AGV to provide feedback to allow the AGV to compensate for inaccuracies in the dead-reckoning. The AGV dead reckoning and position update method is described in U.S. patent applications Ser. Nos. 771,321 and 771,432.
Since the system did not know the intended path of the robot, several problems could occur:
1. The vision system could not know whether an AGV was "on course" because the navigation software had no knowledge of the "course," or intended path. The method disclosed in U.S. patent application Ser. No. 771,329 included a path-predicting technique which could only indicate a best-guess estimate of the next camera to use for a search, assuming the navigation system could identify confidently the AGV's current position. The method did not include a path-planning technique. PA1 2. The number of AGVs the vision system could navigate simultaneously was limited because the amount of message traffic required to properly identify one individual AGV among many was large. PA1 3. The navigation system's speed was limited by lack of knowledge of an AGV's intended path. This method, disclosed in U.S. patent application Ser. No. 771,459, required an ever-increasing radius of search (called rings of uncertainty) when an AGV left a camera's field of view. In a worst case, this could include the entire collection of cameras. PA1 4. Scanning entire fields of view could result in processing insignificant lights, reflections, glare, or lights from the wrong AGV (in case of communication failure). The method disclosed in U.S. patent application Ser. No. 771,380 was used to discriminate between beacon images and extraneous images such as reflections. Even with this "filtering" technique, the image processing windows of the original scheme were so large that AGVs had to remain separated by a wide margin because of the possibility that at least one light of an AGV might intrude into a picture of another, confusing the navigation software. PA1 5. Lack of knowledge about intended motion prevented determining AGV orientation if an AGV light were blocked, as shown in FIG. 1. Previous techniques disclosed in U.S. patent application Ser. No. 772,061 required all of an AGV's lights to be visible to determine orientation. An on-board robot arm or payload obstructed at least one beacon at least 50 percent of the time. The means of determining the location of an obstructed beacon was extrapolation based on knowledge of its most recent known position. AGV control was erratic when robot arms were mounted to the payload area. Any opaque object taller than the beacon mounts could obstruct any or all of the beacons and prevent proper navigation. PA1 6. Positional repeatability suffered because lack of knowledge about nodes in the allowable paths allowed an AGV to approach a given node covered by more than one camera from any direction. To control repeatability, it is desirable to park at a given point always using the same camera. PA1 1. The system controller sends the factory map, with its knowledge of all allowable AGV pathways, camera assignments, and node assignments, to the vision system when the navigation system requests it. This tells the navigation system the location of cameras and nodes within the factory. The navigation system determines the location of the AGVs by processing the beacon images, by computing the centroid of each AGV, and by comparing the centroid with "zones" of travel defined for the AGVs. PA1 2. The navigation system now knows which camera's field of view to check for an AGV at any given time. This greatly decreases the time required to locate an AGV when it leaves a node, thus allowing a larger number of AGVs to operate simultaneously with the navigation system. PA1 3. Now that the vision system contains the factory map, the time required to locate an AGV when it leaves one camera's field of view is greatly reduced. In fact, the navigation system knows not only the absolute position of an AGV of interest, but also the nodes through which it must pass on its way to its intended destination. It therefore knows the camera numbers it should search for the AGV. The software is optimized so that the navigation system normally scans only the camera number under which the AGV is supposed to be traveling at the time of the scan. When the AGV leaves one field of view, the navigation system knows which single camera to scan next, and so forth. It only becomes necessary to scan multiple cameras when an AGV leaves its intended path or when a disabled AGV is enabled. Since the navigation system no longer scans empty space or multiple cameras unnecessarily, its speed is no longer limited by such time-consuming searching. PA1 4. A dynamic image-processing window solves the problem of scanning unrelated lights, reflections, glare, or lights from the wrong AGV. The window corresponds to a processing area only slightly larger than the AGV itself, thus completely excluding the possibility that another AGV can intrude into the image processing area. This also excludes reflections from nearby objects. PA1 5. Now that the navigation system knows where to look for a particular AGV, what direction the AGV was traveling at the last position update, and what its orientation should be, it is possible to navigate an AGV even though its beacons may be partially blocked, as shown in FIG. 1. This is an important improvement because AGVs carrying on-board robot arms or high payloads have at least one beacon blocked at least 50 percent of the time. PA1 6. Positional repeatability is improved at machine nodes (where the AGVs dock) because the navigation system always uses the same camera for parking when more than one camera's field of view overlaps at the node, as shown in FIG. 2. This means that all AGVs which dock at a given node will use the same camera regardless of how they approach the machine node.